package main

func main() {

}

/**
在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，
从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。
你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，
则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。
*/

/*
*
思考：假设我从i位置出发，能达到i+1位置，那必然有cost[i] <= gas[i]

	      假设从i+1位置出发，能达到i+2位置，那么必然有 gas[i]-cost[i]+gas[i+1]>+cost[i+1]
		  所以从i位置出发来到i+1位置时，剩余油量加上i+1位置的油量必须>= 到i+2位置的消耗

得出结论：i位置的余量加上到达i+1位置的剩余油量必须要>=0才能支撑前往i+2位置
*/
func canCompleteCircuit(gas []int, cost []int) int {
	length := len(gas)
	// 初始状态：窗口左右边界都是0，油箱余量为0
	// 窗口左边界不能超过长度
	for start, end, sum := 0, 0, 0; start < length; {
		sum = 0
		// 看油箱余量加上当前位置到下个位置的余量是否大于0
		for sum+gas[end%length]-cost[end%length] >= 0 {
			// 能走完所有站点时，会从这里退出
			// 窗口的长度是否是length了，如果是，则说明走完了所有的位置
			if end-start+1 == length {
				return start
			}
			// 能达到下个位置，加上油箱余量
			sum += gas[end%length] - cost[end%length]
			// 窗口有边界移动
			end++
		}
		// 从 start 位置不能走完所有站点时，start需要从end的下一个位置开始尝试，
		start = end + 1
		end = start
	}
	return -1
}
